﻿//1.按摩师
//https://leetcode.cn/problems/the-masseuse-lcci/

//一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
//在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
//给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
//注意：本题相对原题稍作改动
//示例 1：
//输入：[1, 2, 3, 1]
//输出： 4
//解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
//示例 2：
//输入：[2, 7, 9, 3, 1]
//输出： 12
//解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
//示例 3：
//输入：[2, 1, 4, 5, 3, 1, 1, 3]
//输出： 12
//解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

//解法：
//dp[i]表示：从选到位置i时，此时的最长预约时长
//由题目分析可知，位置i可选也可不选
//所以状态表示可以分情况
//f[i]表示：选到位置i时，位置i必选，此时的最长预约时长
//g[i]表示：选到位置i时，位置i不选，此时的最长预约时长
//(1)f[i]
//由于位置i必选，而位置i - 1必不选，在区间[0,i - 1]的最长预约时长为g[i - 1],再加上位置i的预约时长nums[i] 
//所以f[i] = g[i - 1] + nums[i]
//(2)
//由于位置i不选，而位置i - 1就可选可不选，
//选的话在区间[0,i - 1]的最长预约时长为f[i - 1]
//不选的话在区间[0,i - 1]的最长预约时长为g[i - 1]
//所以g[i] = max(g[i - 1] + f[i - 1])


class Solution {
public:
    int massage(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> f(n), g(n);
        //0位置选的话f[0]就是nums[0]
        //0位置不选的话g[0]就是0
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};


//2.打家劫舍|
//https://leetcode.cn/problems/Gu0c2T/description/
//一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
//影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
//如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
//给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
//示例 1：
//输入：nums = [1, 2, 3, 1]
//输出：4
//解释：偷窃 1 号房屋(金额 = 1) ，然后偷窃 3 号房屋(金额 = 3)。
//偷窃到的最高金额 = 1 + 3 = 4 。
//示例 2：
//输入：nums = [2, 7, 9, 3, 1]
//输出：12
//解释：偷窃 1 号房屋(金额 = 2), 偷窃 3 号房屋(金额 = 9)，接着偷窃 5 号房屋(金额 = 1)。
//偷窃到的最高金额 = 2 + 9 + 1 = 12 。
//提示：
//1 <= nums.length <= 100
//0 <= nums[i] <= 400

//解法：与第一道题"按摩师"类似
//dp[i]表示：偷到位置i时，此时的最大金额
//由题目分析可知，位置i可偷也可不偷
//所以状态表示可以分情况
//f[i]表示：偷到位置i时，位置i必偷，此时的最大金额
//g[i]表示：偷到位置i时，位置i不偷，此时的最大金额
//(1)f[i]
//由于位置i必偷，而位置i - 1必不偷，在区间[0,i - 1]的最最大金额为g[i - 1],再加上位置i的金额nums[i] 
//所以f[i] = g[i - 1] + nums[i]
//(2)
//由于位置i不偷，而位置i - 1就可偷可不偷，
//偷的话在区间[0,i - 1]的最大金额为f[i - 1]
//不偷的话在区间[0,i - 1]的最大金额为g[i - 1]
//所以g[i] = max(g[i - 1] + f[i - 1]
class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> f(n), g(n);
        //0位置偷的话f[0]就是nums[0]
        //0位置不偷的话g[0]就是0
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};


//3.打家劫舍||
//https://leetcode.cn/problems/house-robber-ii/description/
//你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
//这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
//同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
//给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
//示例 1：
//输入：nums = [2, 3, 2]
//输出：3
//解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
//示例 2：
//输入：nums = [1, 2, 3, 1]
//输出：4
//解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
//偷窃到的最高金额 = 1 + 3 = 4 。
//示例 3：
//输入：nums = [1, 2, 3]
//输出：3
//提示：
//1 <= nums.length <= 100
//0 <= nums[i] <= 1000


//解法：与打家劫舍|相比，该题分情况讨论位置0偷还是不偷
//(1)位置0偷的话，在区间[2,n - 2]进行打家劫舍|的方法 
//(2)位置0不偷的话，在区间[1,n - 1]进行打家劫舍|的方法 
//最后取(1)与(2)的最大值


class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        if (n == 3) return max(max(nums[0], nums[1]), nums[2]);
        // n >= 4
        vector<int> f1(n - 3), g1(n - 3);
        f1[0] = nums[2];
        for (int i = 1; i < n - 3; i++)
        {
            f1[i] = g1[i - 1] + nums[i + 2];
            g1[i] = max(g1[i - 1], f1[i - 1]);
        }
        vector<int> f2(n - 1), g2(n - 1);
        f2[0] = nums[1];
        for (int i = 1; i < n - 1; i++)
        {
            f2[i] = g2[i - 1] + nums[i + 1];
            g2[i] = max(g2[i - 1], f2[i - 1]);
        }
        int x = max(f1[n - 4], g1[n - 4]);
        int y = max(f2[n - 2], g2[n - 2]);
        //位置0偷的情况下要加上nums[0]
        return max(nums[0] + x, y);
    }
};


//4.删除并获得点数
//https://leetcode.cn/problems/delete-and-earn/

//给你一个整数数组 nums ，你可以对它进行一些操作。
//每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
//开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
//示例 1：
//输入：nums = [3, 4, 2]
//输出：6
//解释：
//删除 4 获得 4 个点数，因此 3 也被删除。
//之后，删除 2 获得 2 个点数。总共获得 6 个点数。
//示例 2：
//输入：nums = [2, 2, 3, 3, 3, 4]
//输出：9
//解释：
//删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
//之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
//总共获得 9 个点数。
//提示：
//1 <= nums.length <= 2 * 104
//1 <= nums[i] <= 104

//解法：
//将nums中的数与数组arr的下标一一对应
//该问题就转化为在arr数组上进行一次“打家劫舍”问题

class Solution {
public:
    int deleteAndEarn(vector<int>& nums)
    {
        const int N = 10001;
        //1.预处理
        int arr[N] = { 0 };
        for (auto& num : nums)
            arr[num] += num;
        //2.在arr数组上进行一次"打家劫舍"问题
        vector<int> f(N), g(N);
        for (int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[N - 1], g[N - 1]);
    }
};



//5.粉刷房子
//https://leetcode.cn/problems/JEj789/description/
//假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
//当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
//例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
//请计算出粉刷完所有房子最少的花费成本。
//示例 1：
//输入 : costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]
//输出 : 10
//解释 : 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
//最少花费 : 2 + 5 + 3 = 10。
//示例 2：
//输入 : costs = [[7, 6, 2]]
//输出 : 2
//提示 :
//    costs.length == n
//    costs[i].length == 3
//    1 <= n <= 100
//    1 <= costs[i][j] <= 20


//解法：
//状态表示：当涂到位置i时，此时的最小花费，可分为三类
//dp[i][0]表示：当涂到位置i时，选择红色，此时的最小花费
//dp[i][1]表示：当涂到位置i时，选择蓝色，此时的最小花费
//dp[i][2]表示：当涂到位置i时，选择绿色，此时的最小花费
//以第一个状态表示为例：
//当涂到位置i时，选择红色，该位置i的花费是costs[i][0]，而第i - 1位置为蓝色或绿色
//当位置i - 1为蓝色时，位置i - 1的状态表示：dp[i - 1][1]也就是当涂到位置i - 1时，选择蓝色，此时的最小花费
//当位置i - 1为绿色时，位置i - 1的状态表示：dp[i - 1][1]也就是当涂到位置i - 1时，选择绿色，此时的最小花费
//而位置i的最小花费为位置i - 1的最小花费再加上costs[i][0]
//所以dp[i][0] = min(dp[i - 1][1],dp[i - 1][2]) + costs[i][0];
//dp[i][1] 和dp[i][2]依次类推

class Solution {
public:
    int minCost(vector<vector<int>>& costs)
    {
        int n = costs.size();
        //多加一行防止越界和方便填dp表
        vector<vector<int>> dp(n + 1, vector<int>(3));
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        return min(min(dp[n][0], dp[n][1]), dp[n][2]);
    }
};


//6.买卖股票的最佳时机含冷冻期
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
//给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
//设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :
//卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//示例 1:
//输入: prices = [1, 2, 3, 0, 2]
//输出 : 3
//解释 : 对应的交易状态为 : [买入, 卖出, 冷冻期, 买入, 卖出]
//示例 2 :
//输入 : prices = [1]
//输出 : 0
//提示：
//1 <= prices.length <= 5000
//0 <= prices[i] <= 1000

//解法：
//dp[i]表示：第i天之后，获取的最大利润
//由题目分析可知，第i天结束之后有三种状态，分别是“持有股票”、“不持有股票，但处于冷冻期”、“不持有股票，处于可交易”
//将dp[i]分情况讨论，
//dp[i][0]表示：第i天之后，处于“持有股票”状态，此时获取的最大利润  
//dp[i][1]表示：第i天之后，处于“不持有股票，但处于冷冻期”状态，此时获取的最大利润
//dp[i][2]表示：第i天之后，处于“不持有股票，处于可交易”状态，此时获取的最大利润
//“持有股票” 可以状态转移到“不持有股票，但处于冷冻期”状态或仍然处于“持有股票”状态
//“不持有股票，但处于冷冻期”可以状态转移到“不持有股票，处于可交易”状态
//“不持有股票，处于可交易”可以状态转移到“持有股票”状态
// 
//dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
//dp[i][2] = dp[i - 1][0] + prices[i];
class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        //数字0表示“持有股票”，数字1表示“不持有股票，但处于冷冻期”，数字2表示“不持有股票，处于可交易”
        //第0天买入股票
        dp[0][0] = -prices[0];
        // 第0天不可能处于冷冻期
        dp[0][1] = 0;    
        // 第0天不持有股票
        dp[0][2] = 0;         
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};


//7.买卖股票的最佳时机含手续费
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
//给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
//你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
//返回获得利润的最大值。
//注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
//示例 1：
//输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
//输出：8
//解释：能够达到的最大利润 :
//在此处买入 prices[0] = 1
//在此处卖出 prices[3] = 8
//在此处买入 prices[4] = 4
//在此处卖出 prices[5] = 9
//总利润 : ((8 - 1) - 2) + ((9 - 4) - 2) = 8
//示例 2：
//输入：prices = [1, 3, 7, 5, 10, 3], fee = 3
//输出：6
//提示：
//1 <= prices.length <= 5 * 104
//1 <= prices[i] < 5 * 104
//0 <= fee < 5 * 104

//解法：与上一题类似
//dp[i]表示：第i天结束后，此时的最大利润
//由该题知，dp[i]分两种情况，用数字0表示“持有股票”状态，数字1表示“不持有股票，可买入股票”状态
//dp[i][0]表示：第i天结束后，处于“持有股票”状态，此时的最大利润  
//dp[i][1]表示：第i天结束后，处于“不持有股票，可买入股票”状态，此时的最大利润  
//“持有股票”可以状态转移到“不持有股票，可买入股票”状态或仍然处于“持有股票”状态
//“不持有股票，可买入股票”可以状态转移到“持有股票”状态或仍然处于“不持有股票，可买入股票”状态
//dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        //初始化，第0天持有股票
        dp[0][0] = -prices[0];
        //第0天不买入股票
        dp[0][1] = 0;
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[n - 1][1];
    }
};


//8.买卖股票的最佳时机|||
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//示例 1:
//输入：prices = [3, 3, 5, 0, 0, 3, 1, 4]
//输出：6
//解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3 。
//随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4 - 1 = 3 。
//示例 2：
//输入：prices = [1, 2, 3, 4, 5]
//输出：4
//解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
//注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
//因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
//示例 3：
//输入：prices = [7, 6, 4, 3, 1]
//输出：0
//解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
//示例 4：
//输入：prices = [1]
//输出：0
//提示：
//1 <= prices.length <= 105
//0 <= prices[i] <= 105

//解法:
//dp[i][j]表示：第i天结束后，完成了j次交易，此时的最大利润
//由题知，dp[i][j]分两种情况，分别是
//(1)第i天结束后，完成了j次交易，手中是“持有股票”状态，此时的最大利润
//(2)第i天结束后，完成了j次交易，手中是“不持有股票，可买入股票”状态，此时的最大利润
//用f[i][j]表示：第i天结束后，完成了j次交易，手中是“持有股票”状态，此时的最大利润
//用g[i][j]表示：第i天结束后，完成了j次交易，手中是“不持有股票，可买入股票”状态，此时的最大利润
//“持有股票”可以状态转移到“不持有股票，可买入股票”状态或仍然处于“持有股票”状态
//“不持有股票，可买入股票”可以状态转移到“持有股票”状态或仍然处于“不持有股票，可买入股票”状态
//f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//g[i][j] = g[i - 1][j];
//if (j - 1 >= 0)
//g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
class Solution {
public:
    //不用INT_MIN是为了防止 -INT_MIN 减去一个正数溢出变成一个值极大的整数影响结果
    const int INF = 0x3f3f3f;
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF));
        auto g = f;
        //初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++)
            for (int j = 0; j < 3; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        //找到最后以后一行的最大值
        int ret = 0;
        for (int j = 0; j < 3; j++)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};



//9.买卖股票的最佳时机||||
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
//给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//示例 1：
//输入：k = 2, prices = [2, 4, 1]
//输出：2
//解释：在第 1 天(股票价格 = 2) 的时候买入，在第 2 天(股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2 。
//示例 2：
//输入：k = 2, prices = [3, 2, 6, 5, 0, 3]
//输出：7
//解释：在第 2 天(股票价格 = 2) 的时候买入，在第 3 天(股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6 - 2 = 4 。
//随后，在第 5 天(股票价格 = 0) 的时候买入，在第 6 天(股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3 - 0 = 3 。
//提示：
//1 <= k <= 100
//1 <= prices.length <= 1000
//0 <= prices[i] <= 1000


//解法:与上题一致
class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -INF));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++)
            for (int j = 0; j < k + 1; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        //找到最后以后一行的最大值
        int ret = 0;
        for (int j = 0; j < k + 1; j++)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};
